//===- bloom.cpp - Andersen's Interprocedural Alias Analysis using bloom filters ----------===//

#define DEBUG_TYPE "anders-aa"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BasicCallGraph.h"
#include <time.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
using namespace llvm;

STATISTIC(NumIters            , "Number of iterations to reach convergence");
//STATISTIC(NumConstraints      , "Number of constraints");
STATISTIC(NumNodes            , "Number of nodes");
STATISTIC(NumEscapingFunctions, "Number of internal functions that escape");
STATISTIC(NumIndirectCallees  , "Number of indirect callees found");

typedef std::pair<CallSite,CallGraphNode*> CallRecord;
void *latestretnode = NULL;
std::map<CallRecord, bool> processed;
std::map<CallGraphNode *, bool> incallchain;
CallGraphNode *groot = NULL;
std::map<Value *, bool> funprocessed;

#define NBF	80000000
#define BFSIZE (3*NBF/4 + 1)
#define BFUNISIZE (NBF/4 + 1)
#define POINTEEMAX 53
#define ALMOST_FULL 10
#define CONTEXTMAX 17
#define CONTEXTPOINTEEMAX POINTEEMAX/CONTEXTMAX

#define NBFKAUSHIK 30
#define NHASH 1		// no of hash functions: check addpointerto, copyfrom, alias AND constructor of Node.

bool bf[BFSIZE];	// sets one byte for each bool.
/*bool bf2[NBF/3];	// sets one byte for each bool.
bool bf3[NBF/3];	// sets one byte for each bool.*/
//bool bfuni[BFUNISIZE];

clock_t cross_starttime, cross_endtime;
double cross_inittime, cross_cctime, cross_sctime;
double cross_bloomtime = 0;	// time spent in bloom operations during solve constraints.

namespace {
  class VISIBILITY_HIDDEN Andersens : public ModulePass, public AliasAnalysis,
                                      private InstVisitor<Andersens> {
  public:
    static char ID; // Class identification, replacement for typeinfo
    Andersens() : ModulePass((intptr_t)&ID) {}
    /// Node class - This class is used to represent a memory object in the
    /// program, and is the primitive used to build the points-to graph.
    class Node;
    typedef std::vector<CallGraphNode *> One;
    struct CrossContext {
	One callchain;
	std::vector<CallSite> cscallchain;
	std::vector<Node *> Pointees;
    };
    typedef struct CrossContext CrossContext;
    typedef CrossContext Two;

  public:
    class Node {
      Value *Val;
    public:
      //std::vector<Node*> Pointees;
      std::map<One, Two *> contexts;
      bool mybloom[NHASH][NBFKAUSHIK+2];	// this stores local pointer info for all contexts. +2 for universal.
      bool iamaptr;
      static const unsigned ID; // Pass identification, replacement for typeid
      Node() : Val(0) {contexts.clear(); iamaptr = false; for(unsigned ii = 0; ii < NBFKAUSHIK; ++ii)for (unsigned jj=0; jj < NHASH; ++jj){ mybloom[jj][ii] = false;}}
      Node *setValue(Value *V) {
        /////assert(Val == 0 && "Value already set for this node!");
        Val = V;
        return this;
      }
      unsigned getsize() {
	unsigned mem = 0;	// sizeof(Node).
	if (iamaptr) { mem += NHASH*NBFKAUSHIK; }
	return mem;
      }

      bool issubset(const One &, const One &) const;
      bool issubset(const std::vector<CallSite> &, const std::vector<CallSite> &) const;
      /// getValue - Return the LLVM value corresponding to this node.
      ///
      Value *getValue() const { return Val; }

      typedef std::vector<Node*>::const_iterator iterator;
      /*iterator begin() const { return Pointees.begin(); }
      iterator end() const { return Pointees.end(); }*/

      /// addPointerTo - Add a pointer to the list of pointees of this node,
      /// returning true if this caused a new pointer to be added, or false if
      /// we already knew about the points-to relation.
      bool addPointerTo(Node *N, CrossContext &context) {
	cross_addpointerto(this, N, context);
	return false;
	CrossContext *cc = contexts[context.callchain];
	if (!cc) {
		cc = contexts[context.callchain] = new CrossContext();
		cc->callchain = context.callchain;
		cc->cscallchain = context.cscallchain;
	}

        std::vector<Node*>::iterator I = std::lower_bound(cc->Pointees.begin(),
                                                          cc->Pointees.end(),
                                                          N);
        if (I != cc->Pointees.end() && *I == N)
          return false;
        cc->Pointees.insert(I, N);
        return true;
      }
      void cross_addpointerto(Node *pointernode, Node *pointeenode, Andersens::CrossContext &context);

      /// intersects - Return true if the points-to set of this node intersects
      /// with the points-to set of the specified node.
      bool intersects(Node *N) const;

      /// intersectsIgnoring - Return true if the points-to set of this node
      /// intersects with the points-to set of the specified node on any nodes
      /// except for the specified node to ignore.
      bool intersectsIgnoring(Node *N, Node *Ignoring) const;

      // Constraint application methods.
      bool copyFrom(Node *N, const CrossContext &, const CrossContext &);
      bool loadFrom(Node *N, CrossContext &, CrossContext &);
      bool storeThrough(Node *N, CrossContext &, CrossContext &);

    };

    /// GraphNodes - This vector is populated as part of the object
    /// identification stage of the analysis, which populates this vector with a
    /// node for each memory object and fills in the ValueNodes map.
    CallGraphNode *currentp;

    /// ValueNodes - This map indicates the Node that a particular Value* is
    /// represented by.  This contains entries for all pointers.
    std::map<Value*, unsigned> ValueNodes;
    std::map<Value*, unsigned> gvalues;

    /// ObjectNodes - This map contains entries for each memory object in the
    /// program: globals, alloca's and mallocs.
    std::map<Value*, unsigned> ObjectNodes;

    /// ReturnNodes - This map contains an entry for each function in the
    /// program that returns a value.
    std::map<Function*, unsigned> ReturnNodes;

    /// VarargNodes - This map contains the entry used to represent all pointers
    /// passed through the varargs portion of a function call for a particular
    /// function.  An entry is not present in this map for functions that do not
    /// take variable arguments.
    std::map<Function*, unsigned> VarargNodes;

    /// Constraint - Objects of this structure are used to represent the various
    /// constraints identified by the algorithm.  The constraints are 'copy',
    /// for statements like "A = B", 'load' for statements like "A = *B", and
    /// 'store' for statements like "*A = B".
    struct Constraint {
      enum ConstraintType { Copy, Load, Store } Type;
      Node *Dest, *Src;
      CrossContext context;	// use currentcontext to fill this up.

      Constraint(ConstraintType Ty, Node *D, Node *S)
        : Type(Ty), Dest(D), Src(S) {
   		extern CrossContext emptycontext;
		context = emptycontext;
      }
      Constraint(ConstraintType Ty, Node *D, Node *S, bool usecurrentcontext)
        : Type(Ty), Dest(D), Src(S) {
   		extern CrossContext currentcontext;
		context = currentcontext;
      }
    };

    /// Constraints - This vector contains a list of all of the constraints
    /// identified by the program.
    std::vector<Constraint> Constraints;

    /// EscapingInternalFunctions - This set contains all of the internal
    /// functions that are found to escape from the program.  If the address of
    /// an internal function is passed to an external function or otherwise
    /// escapes from the analyzed portion of the program, we must assume that
    /// any pointer arguments can alias the universal node.  This set keeps
    /// track of those functions we are assuming to escape so far.
    std::set<Function*> EscapingInternalFunctions;

    /// IndirectCalls - This contains a list of all of the indirect call sites
    /// in the program.  Since the call graph is iteratively discovered, we may
    /// need to add constraints to our graph as we find new targets of function
    /// pointers.
    std::vector<CallSite> IndirectCalls;

    /// IndirectCallees - For each call site in the indirect calls list, keep
    /// track of the callees that we have discovered so far.  As the analysis
    /// proceeds, more callees are discovered, until the call graph finally
    /// stabilizes.
    std::map<CallSite, std::vector<Function*> > IndirectCallees;

    /// This enum defines the GraphNodes indices that correspond to important
    /// fixed sets.
    enum {
      UniversalSet = 0,
      NullPtr      = 1,
      NullObject   = 2
    };

  public:
    void findderefsize();
    void AnalyzeCallGraph(BasicCallGraph &CG, Module &M);
    void initglobals(Module &M);
    void metavisit(CallSite &cs, CallGraphNode *p);
    int processfront(CallSite &cs, CallGraphNode *&p, bool processingspecial);
    void processback(CallSite &cs, CallGraphNode *p, bool processingspecial);
    void cross_histogram();
    void cross_init() {
        //bf.reserve(NBF);
	for (unsigned ii = 0; ii < BFSIZE; ++ii) {
		bf[ii] = false;
	}
	//univalues.clear();
    }
 
 	void printtimes() {
		cout << "init time                = " << cross_inittime/CLOCKS_PER_SEC << " sec.\n";
		cout << "collect constraints time = " << cross_cctime/CLOCKS_PER_SEC   << " sec.\n";
		cout << "solve constraints time   = " << cross_sctime/CLOCKS_PER_SEC   << " sec.\n";
		cout << "bloom ops time           = -" << cross_bloomtime/CLOCKS_PER_SEC<< " sec.\n";
	}
      void calculateTypes(Module &M);
      bool isptop(Value *V);

    bool runOnModule(Module &M) {
    extern std::vector<Andersens::Node> GraphNodes;
    	calculateTypes(M);
    	cross_starttime = clock();
	cross_init();
      InitializeAliasAnalysis(this);
    	cross_endtime = clock();
	cross_inittime = cross_endtime - cross_starttime;
      IdentifyObjects(M);
      /*CollectConstraints(M);
      DEBUG(PrintConstraints());*/
      AnalyzeCallGraph(getAnalysis<BasicCallGraph>(), M); // Propagate on CG
    	cross_starttime = clock();
	cross_cctime = cross_starttime - cross_endtime;
      SolveConstraints();
    	cross_endtime = clock();
	cross_sctime = cross_endtime - cross_starttime;
      //PrintPointsToGraph();
      //cross_histogram();
      /*cerr << "sizeof(Node) = " << sizeof(Node) << "\n";
      cerr << "no of nodes = " << GraphNodes.size() << "\n";
      findderefsize();

	std::cout << "sizeof(node) = " << sizeof(Node) << "\n";*/
	unsigned mem = 0;
	unsigned nptr = 0;
	for (unsigned ii = 0; ii < GraphNodes.size(); ++ii) {
		mem += GraphNodes[ii].getsize();
		if (GraphNodes[ii].iamaptr) ++nptr;
	}
	mem /= 8;	// the size was in bytes.
	mem += 16*GraphNodes.size();
	//mem += 16*GraphNodes.size();	// size of the mapping from value->node.
	std::cout << "Memory requirement = " << mem/1000.0 << " KB.\n";
	std::cout << "No of pointers = " << nptr << "\n";
	//std::cout << "No of nodes = " << GraphNodes.size() << std::endl;
	//std::cout << "Total size = nodes * sizeof(node) = " << GraphNodes.size() << " * " << sizeof(Node) << " = " << GraphNodes.size() * sizeof(Node) << std::endl;
	//printtimes();
      // Free the constraints list, as we don't need it to respond to alias
      // requests.
      ObjectNodes.clear();
      ReturnNodes.clear();
      VarargNodes.clear();
      EscapingInternalFunctions.clear();
      std::vector<Constraint>().swap(Constraints);
      return false;
    }

      /*bool pointstouniversal(Node *N) {
	if (N->Pointees.size() && N->Pointees[0] == &GraphNodes[UniversalSet]) {
		return true;
	}
	return false;
      }*/
    void releaseMemory() {
      // FIXME: Until we have transitively required passes working correctly,
      // this cannot be enabled!  Otherwise, using -count-aa with the pass
      // causes memory to be freed too early. :(
#if 0
      extern std::vector<Node> GraphNodes;
      // The memory objects and ValueNodes data structures at the only ones that
      // are still live after construction.
      std::vector<Node>().swap(GraphNodes);
      ValueNodes.clear();
#endif
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AliasAnalysis::getAnalysisUsage(AU);
      AU.addRequired<BasicCallGraph>();
      AU.setPreservesAll();                         // Does not transform code
    }

    //------------------------------------------------
    // Implement the AliasAnalysis API
    //
    AliasResult alias(const Value *V1, unsigned V1Size,
                      const Value *V2, unsigned V2Size);
    virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
    virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
    virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
    virtual bool pointsToConstantMemory(const Value *P);
    virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, std::vector<PointerAccessInfo> *Info = 0);

    virtual void deleteValue(Value *V) {
      ValueNodes.erase(V);
      getAnalysis<AliasAnalysis>().deleteValue(V);
    }

    virtual void copyValue(Value *From, Value *To) {
      ValueNodes[To] = ValueNodes[From];
      getAnalysis<AliasAnalysis>().copyValue(From, To);
    }

  private:
    /// getNode - Return the node corresponding to the specified pointer scalar.
    ///
    Node *getNode(Value *V) {
      extern std::vector<Node> GraphNodes;
      if (Constant *C = dyn_cast<Constant>(V))
        if (!isa<GlobalValue>(C))
          return getNodeForConstantPointer(C);

      std::map<Value*, unsigned>::iterator I = ValueNodes.find(V);
      if (I == ValueNodes.end()) {
#ifndef NDEBUG
        V->dump();
#endif
	return &GraphNodes[UniversalSet];
      }
      return &GraphNodes[I->second];
    }

    /// getObject - Return the node corresponding to the memory object for the
    /// specified global or allocation instruction.
    Node *getObject(Value *V) {
      extern std::vector<Node> GraphNodes;
      std::map<Value*, unsigned>::iterator I = ObjectNodes.find(V);
      assert(I != ObjectNodes.end() &&
             "Value does not have an object in the points-to graph!");
      return &GraphNodes[I->second];
    }

    /// getReturnNode - Return the node representing the return value for the
    /// specified function.
    Node *getReturnNode(Function *F) {
      extern std::vector<Node> GraphNodes;
      std::map<Function*, unsigned>::iterator I = ReturnNodes.find(F);
      assert(I != ReturnNodes.end() && "Function does not return a value!");
      return &GraphNodes[I->second];
    }

    /// getVarargNode - Return the node representing the variable arguments
    /// formal for the specified function.
    Node *getVarargNode(Function *F) {
      extern std::vector<Node> GraphNodes;
      std::map<Function*, unsigned>::iterator I = VarargNodes.find(F);
      assert(I != VarargNodes.end() && "Function does not take var args!");
      return &GraphNodes[I->second];
    }

    /// getNodeValue - Get the node for the specified LLVM value and set the
    /// value for it to be the specified value.
    Node *getNodeValue(Value &V) {
      return getNode(&V)->setValue(&V);
    }

    void IdentifyObjects(Module &M);
    void CollectConstraints(Module &M);
    void SolveConstraints();

    Node *getNodeForConstantPointer(Constant *C);
    Node *getNodeForConstantPointerTarget(Constant *C);
    void AddGlobalInitializerConstraints(Node *N, Constant *C);

    void AddConstraintsForNonInternalLinkage(Function *F);
    void AddConstraintsForCall(CallSite CS, Function *F);
    bool AddConstraintsForExternalCall(CallSite CS, Function *F);


    void PrintNode(Node *N);
    void PrintConstraints();
    void PrintPointsToGraph();
    void printcontext(const One &);
    void printpointees(Two *);

    //===------------------------------------------------------------------===//
    // Instruction visitation methods for adding constraints
    //
    friend class InstVisitor<Andersens>;
    void visitReturnInst(ReturnInst &RI);
    void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); }
    void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); }
    void visitCallSite(CallSite CS);
    void visitAllocationInst(AllocationInst &AI);
    void visitLoadInst(LoadInst &LI);
    void visitStoreInst(StoreInst &SI);
    void visitGetElementPtrInst(GetElementPtrInst &GEP);
    void visitPHINode(PHINode &PN);
    void visitCastInst(CastInst &CI);
    void visitICmpInst(ICmpInst &ICI) {} // NOOP!
    void visitFCmpInst(FCmpInst &ICI) {} // NOOP!
    void visitSelectInst(SelectInst &SI);
    void visitVAArg(VAArgInst &I);
    void visitInstruction(Instruction &I);
  };

    std::vector<Andersens::Node> GraphNodes;
  Andersens::CrossContext currentcontext;	// empty means global context. never use currentcontext.Pointees.
  Andersens::CrossContext const emptycontext;	// empty means global context. never write to this.
  char Andersens::ID = 0;
  RegisterPass<Andersens> X("anders-aa",
                            "Andersen's Interprocedural Alias Analysis");
  RegisterAnalysisGroup<AliasAnalysis> Y(X);
}


ModulePass *llvm::createAndersensPass() { return new Andersens(); }

//===----------------------------------------------------------------------===//
//                  AliasAnalysis Interface Implementation
//===----------------------------------------------------------------------===//

unsigned cross_hash1(unsigned V1) {
	unsigned h = ~V1;
	h ^= (V1 << 4);
	return h % BFSIZE;
}
unsigned cross_hash2(unsigned V1) {
	unsigned h = V1;
	h |= (V1 >> 8);
	//pointeeshash2[h%POINTEEMAX].insert((Value *)V1);
	return h % NBFKAUSHIK;
}
unsigned cross_hash3(unsigned V1) {
	unsigned h = 0;
	h += (V1 << 4) >> 8;
	h += (V1 << 16) >> 8;
	return h % BFSIZE;
}
unsigned cross_hash4(unsigned V1) {
	unsigned h = 0;
	for (int ii = 4; ii < 28; ++ii) {
		h += (5 + ii) * ((V1 << ii) >> 31);
	}
	return h % NBFKAUSHIK;
}
unsigned cross_hash5(unsigned V1) {
	unsigned h = 0;
	for (int ii = 0; ii < 8; ++ii) {
		h += (V1 & 0xf) * 111;
		V1 >>= 4;
	}
	return h % BFSIZE;
}
unsigned cross_hash6(unsigned V1) {
	unsigned h = 0;
	for (int ii = 0; ii < 8; ++ii) {
		h += (V1 & 0xf) * 123;
		V1 >>= 4;
	}
	return h % NBFKAUSHIK;
}
unsigned cross_hash7(unsigned V1) {
	unsigned h = 1;
	for (int ii = 0; ii < 32; ++ii) {
		h <<= 1;
		V1 >>= 1;
		h += (V1 % 2);
	}
	// h == V1 reversed.
	h ^= V1;
	return h % BFSIZE;
}

unsigned cross_hashc1(Andersens::CrossContext &context) {
	// derive hash from the callchain.
	unsigned h = 0;
	Andersens::One callchain = context.callchain;
	for (std::vector<CallGraphNode *>::iterator it = callchain.begin(); it != callchain.end(); ++it) {
		h ^= (unsigned)*it;
	}
	return h % CONTEXTMAX;
}
void cross_addtouniversal(bool *to) {
	//guniversal.push_back(to);
	//guniversal.insert(to);
	to[NBFKAUSHIK + 1] = true;
	to[NBFKAUSHIK + 2] = true;
}
bool cross_pointstouniversal(bool *to) {
	/*for (std::vector<unsigned>::iterator it = guniversal.begin(); it != guniversal.end(); ++it) {
		if (*it == to) {
			return true;
		}
	}
	return false;*/
	/*if (guniversal.find(to) == guniversal.end()) {
		return false;
	}
	return true;*/
	if (to[NBFKAUSHIK + 1] && to[NBFKAUSHIK + 2]) {
		return true;
	}
	return false;
}
bool cross_pointstouniversalvalue(Andersens::Node *ptr) {
	return cross_pointstouniversal(ptr->mybloom[0]);
}
bool cross_pointstosomeone(Andersens::Node *ptr) {
	bool empty0 = true, empty1 = true, empty2 = true;
	for (unsigned ii = 0; ii < NBFKAUSHIK; ++ii) {
		if (ptr->mybloom[0][ii]) {
			empty0 = false;
		}
	}
	if (empty0) {
		return false;
	}
	return true;
}
void Andersens::Node::cross_addpointerto(Node *pointernode, Node *pointeenode, Andersens::CrossContext &contextcontext) {
	if (pointernode == NULL || pointeenode == NULL) {
		return;
	}
	Value *pointerval = pointernode->getValue();
	Value *pointeeval = pointeenode->getValue();
	unsigned pointer, context, pointee;

	pointer = cross_hash1((unsigned)pointerval);
	context = cross_hashc1(contextcontext);
	pointee = cross_hash2((unsigned)pointeeval);

	pointernode->iamaptr = true;
	if (pointeenode == &GraphNodes[UniversalSet]) {
		cross_addtouniversal(pointernode->mybloom[0]);
	} else if (pointeenode == &GraphNodes[NullObject]) {

	} else {
		unsigned offset = (context*CONTEXTPOINTEEMAX + pointee);
		//bf[(pointer + (offset)) % BFSIZE] = true;
		pointernode->mybloom[0][offset % NBFKAUSHIK] = true;

	}
}

bool cross_copyfrom_primitive(bool *to, bool *from, Andersens::CrossContext &contextcontext, int whichbf) {
	if (whichbf == 1 && cross_pointstouniversal(from)) {
		cross_addtouniversal(to);
	}
	for (unsigned ii = 0; ii < NBFKAUSHIK; ++ii) {
		to[ii] = to[ii] || from[ii];
	}
	return false;	//// this should be more intelligent.
}
bool cross_copyfrom(Andersens::Node *dstnode, Andersens::Node *srcnode, Andersens::CrossContext &context) {
	bool changed = false;
	bool *fromptr, *toptr;

	if (dstnode == NULL || srcnode == NULL) {
		return false;
	}
	dstnode->iamaptr = true;

	for (unsigned ii = 0; ii < NHASH; ++ii) {
		fromptr = srcnode->mybloom[ii];
		toptr = dstnode->mybloom[ii];
		changed = cross_copyfrom_primitive(toptr, fromptr, context, ii+1) || changed;	// order is imp.
	}

	return changed;
}
void Andersens::cross_histogram() {
	unsigned unit = 1000;
	unsigned nones = 0, nsum = 0;
	unsigned int maxononeline = 10;
	unsigned ononeline = 0;

	for (unsigned ii = 0; ii < BFSIZE; ++ii) {
		if (bf[ii]) {
			++nones;
		}
		//nsum += countingbf[ii];
		if ((ii+1) % unit == 0) {
			std::cerr << /*ii << ": " <<*/ nones;
			//std::cerr << nsum;
			if (++ononeline == maxononeline) {
				std::cerr << '\n';
				ononeline = 0;
			} else {
				std::cerr << '\t';
			}
			nones = 0;
			nsum = 0;
		}
	}
}
bool cross_alias(Andersens::Node *V1, Andersens::Node *V2) {
//bool cross_alias(const Value *V1, const Value *V2) {
	for (unsigned ii = 0; ii < NBFKAUSHIK; ++ii) {
		if (V1->mybloom[0][ii] && V2->mybloom[0][ii] &&
		    true) {
			return true;
		}
	}
	return false;
}
AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size,
                                            const Value *V2, unsigned V2Size) {
  Node *N1 = getNode(const_cast<Value*>(V1));
  Node *N2 = getNode(const_cast<Value*>(V2));

	if (!cross_alias(N1, N2)) {
		return NoAlias;
	} else {
		return MayAlias;
	}
}

AliasAnalysis::ModRefResult
Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
  // The only thing useful that we can contribute for mod/ref information is
  // when calling external function calls: if we know that memory never escapes
  // from the program, it cannot be modified by an external call.
  //
  // NOTE: This is not really safe, at least not when the entire program is not
  // available.  The deal is that the external function could call back into the
  // program and modify stuff.  We ignore this technical niggle for now.  This
  // is, after all, a "research quality" implementation of Andersen's analysis.
      Node *N1 = getNode(P);
  if (Function *F = CS.getCalledFunction())
    if (F->isDeclaration()) {

      if (!cross_pointstosomeone(N1)) return NoModRef;
      if (!cross_pointstouniversalvalue(N1)) return NoModRef;
    }

  return AliasAnalysis::getModRefInfo(CS, P, Size);
}

AliasAnalysis::ModRefResult
Andersens::getModRefInfo(CallSite CS1, CallSite CS2) {
  return AliasAnalysis::getModRefInfo(CS1,CS2);
}

AliasAnalysis::ModRefBehavior
Andersens::getModRefBehavior(Function *F, CallSite CS,
                                 std::vector<PointerAccessInfo> *Info) {
  unsigned mask = (unsigned)NoModRef;

  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
    if (I->mayWriteToMemory()) {
	Node *N = getNode(&*I);
	if (cross_pointstosomeone(N)) {
		mask |= (unsigned)Mod;
	}
    } else {
	if (I->getOpcode() == Instruction::Malloc || I->getOpcode() == Instruction::Free || I->getOpcode() == Instruction::Alloca ||
	    I->getOpcode() == Instruction::Load || I->getOpcode() == Instruction::Store) {
		Node *N = getNode(&*I);
		if (cross_pointstosomeone(N)) {
			mask |= (unsigned)Ref;
		}
	}
    }
  }
  if (mask == NoModRef) return DoesNotAccessMemory;
  if (mask == Ref) return OnlyReadsMemory;
  return UnknownModRefBehavior;
}
/// getMustAlias - We can provide must alias information if we know that a
/// pointer can only point to a specific function or the null pointer.
/// Unfortunately we cannot determine must-alias information for global
/// variables or any other memory memory objects because we do not track whether
/// a pointer points to the beginning of an object or a field of it.
void Andersens::getMustAliases(Value *P, std::vector<Value*> &RetVals) {
  AliasAnalysis::getMustAliases(P, RetVals);
}

/// pointsToConstantMemory - If we can determine that this pointer only points
/// to constant memory, return true.  In practice, this means that if the
/// pointer can only point to constant globals, functions, or the null pointer,
/// return true.
///
bool Andersens::pointsToConstantMemory(const Value *P) {
        return AliasAnalysis::pointsToConstantMemory(P);
}
bool Andersens::isptop(Value *V) {
	if (isa<PointerType>(V->getType())) {
		//cerr << getTypeDescription(V->getType()) << "\n";
		//enum Type::TypeID tid = V->getType()->getTypeID();
		//const Type *ptype = Type::getPrimitiveType(tid);
		//const Type *type0 = dyn_cast<CompositeType>(V->getType())->getTypeAtIndex(V);
		const Type *type1 = dyn_cast<PointerType>(V->getType())->getElementType();
		if (type1 && isa<PointerType>(type1)) {
			//const Type *type11 = dyn_cast<PointerType>(type1)->getElementType();
			//if (type11 && isa<PointerType>(type11)) {
				return true;
			//}
		}
	}
	return false;
}
void Andersens::calculateTypes(Module &M) {
  unsigned nvars = 0;
  unsigned nptop = 0;
  for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) {
	++nvars;
	if (isptop(I)) ++nptop;
  }
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
    for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
      if (isa<AllocationInst>(&*II)) {
	++nvars;
	if (isptop(&*II)) ++nptop;
      }
    }  
  }
  cerr << "pointers to pointers = " << nptop << "/" << nvars << " = " << nptop*100.0/nvars << "%.\n";
}
//===----------------------------------------------------------------------===//
//                       Object Identification Phase
//===----------------------------------------------------------------------===//

/// IdentifyObjects - This stage scans the program, adding an entry to the
/// GraphNodes list for each memory object in the program (global stack or
/// heap), and populates the ValueNodes and ObjectNodes maps for these objects.
///
void Andersens::IdentifyObjects(Module &M) {
  unsigned NumObjects = 0;

  // Object #0 is always the universal set: the object that we don't know
  // anything about.
  assert(NumObjects == UniversalSet && "Something changed!");
  ++NumObjects;

  // Object #1 always represents the null pointer.
  assert(NumObjects == NullPtr && "Something changed!");
  ++NumObjects;

  // Object #2 always represents the null object (the object pointed to by null)
  assert(NumObjects == NullObject && "Something changed!");
  ++NumObjects;

  // Add all the globals first.
  for (Module::global_iterator I = M.global_begin(), E = M.global_end();
       I != E; ++I) {
    ObjectNodes[I] = NumObjects++;
    ValueNodes[I] = NumObjects++;
  }

  // Add nodes for all of the functions and the instructions inside of them.
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
    // The function itself is a memory object.
    ValueNodes[F] = NumObjects++;
    ObjectNodes[F] = NumObjects++;
    if (isa<PointerType>(F->getFunctionType()->getReturnType()))
      ReturnNodes[F] = NumObjects++;
    if (F->getFunctionType()->isVarArg())
      VarargNodes[F] = NumObjects++;

    // Add nodes for all of the incoming pointer arguments.
    for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
         I != E; ++I)
      if (isa<PointerType>(I->getType()))
        ValueNodes[I] = NumObjects++;

    // Scan the function body, creating a memory object for each heap/stack
    // allocation in the body of the function and a node to represent all
    // pointer values defined by instructions and used as operands.
    for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
      // If this is an heap or stack allocation, create a node for the memory
      // object.
      if (isa<PointerType>(II->getType())) {
        ValueNodes[&*II] = NumObjects++;
        if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II))
          ObjectNodes[AI] = NumObjects++;
      }
    }
  }

  // Now that we know how many objects to create, make them all now!
  GraphNodes.resize(NumObjects);
  NumNodes += NumObjects;
}

//===----------------------------------------------------------------------===//
//                     Constraint Identification Phase
//===----------------------------------------------------------------------===//

/// getNodeForConstantPointer - Return the node corresponding to the constant
/// pointer itself.
Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) {
  assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");

  if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C))
    return &GraphNodes[NullPtr];
  else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
    return getNode(GV);
  else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
    switch (CE->getOpcode()) {
    case Instruction::GetElementPtr:
      return getNodeForConstantPointer(CE->getOperand(0));
    case Instruction::IntToPtr:
      return &GraphNodes[UniversalSet];
    case Instruction::BitCast:
      return getNodeForConstantPointer(CE->getOperand(0));
    default:
      cerr << "Constant Expr not yet handled: " << *CE << "\n";
      assert(0);
    }
  } else {
    assert(0 && "Unknown constant pointer!");
  }
  return 0;
}

/// getNodeForConstantPointerTarget - Return the node POINTED TO by the
/// specified constant pointer.
Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) {
  assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");

  if (isa<ConstantPointerNull>(C))
    return &GraphNodes[NullObject];
  else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
    return getObject(GV);
  else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
    switch (CE->getOpcode()) {
    case Instruction::GetElementPtr:
      return getNodeForConstantPointerTarget(CE->getOperand(0));
    case Instruction::IntToPtr:
      return &GraphNodes[UniversalSet];
    case Instruction::BitCast:
      return getNodeForConstantPointerTarget(CE->getOperand(0));
    default:
      cerr << "Constant Expr not yet handled: " << *CE << "\n";
      assert(0);
    }
  } else {
    assert(0 && "Unknown constant pointer!");
  }
  return 0;
}

/// AddGlobalInitializerConstraints - Add inclusion constraints for the memory
/// object N, which contains values indicated by C.
void Andersens::AddGlobalInitializerConstraints(Node *N, Constant *C) {
  if (C->getType()->isFirstClassType()) {
    if (isa<PointerType>(C->getType()))
      N->copyFrom(getNodeForConstantPointer(C), currentcontext, currentcontext);

  } else if (C->isNullValue()) {
    N->addPointerTo(&GraphNodes[NullObject], currentcontext);
    return;
  } else if (!isa<UndefValue>(C)) {
    // If this is an array or struct, include constraints for each element.
    assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C));
    for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
      AddGlobalInitializerConstraints(N, cast<Constant>(C->getOperand(i)));
  }
}

/// AddConstraintsForNonInternalLinkage - If this function does not have
/// internal linkage, realize that we can't trust anything passed into or
/// returned by this function.
void Andersens::AddConstraintsForNonInternalLinkage(Function *F) {
  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
    if (isa<PointerType>(I->getType()))
      // If this is an argument of an externally accessible function, the
      // incoming pointer might point to anything.
      Constraints.push_back(Constraint(Constraint::Copy, getNode(I),
                                       &GraphNodes[UniversalSet]));
}

/// AddConstraintsForExternalCall - If this is a call to a "known" function, add the
/// constraints and return true.  If this is a call to an unknown function,
/// return false.
bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) {
  assert(F->isDeclaration() && "Not an external function!");
  //cout << "addconsforextcall.\n";

  // These functions don't induce any points-to constraints.
  if (F->getName() == "atoi" || F->getName() == "atof" ||
      F->getName() == "atol" || F->getName() == "atoll" ||
      F->getName() == "remove" || F->getName() == "unlink" ||
      F->getName() == "rename" || F->getName() == "memcmp" ||
      F->getName() == "llvm.memset.i32" ||
      F->getName() == "llvm.memset.i64" ||
      F->getName() == "strcmp" || F->getName() == "strncmp" ||
      F->getName() == "execl" || F->getName() == "execlp" ||
      F->getName() == "execle" || F->getName() == "execv" ||
      F->getName() == "execvp" || F->getName() == "chmod" ||
      F->getName() == "puts" || F->getName() == "write" ||
      F->getName() == "open" || F->getName() == "create" ||
      F->getName() == "truncate" || F->getName() == "chdir" ||
      F->getName() == "mkdir" || F->getName() == "rmdir" ||
      F->getName() == "read" || F->getName() == "pipe" ||
      F->getName() == "wait" || F->getName() == "time" ||
      F->getName() == "stat" || F->getName() == "fstat" ||
      F->getName() == "lstat" || F->getName() == "strtod" ||
      F->getName() == "strtof" || F->getName() == "strtold" ||
      F->getName() == "fopen" || F->getName() == "fdopen" ||
      F->getName() == "freopen" ||
      F->getName() == "fflush" || F->getName() == "feof" ||
      F->getName() == "fileno" || F->getName() == "clearerr" ||
      F->getName() == "rewind" || F->getName() == "ftell" ||
      F->getName() == "ferror" || F->getName() == "fgetc" ||
      F->getName() == "fgetc" || F->getName() == "_IO_getc" ||
      F->getName() == "fwrite" || F->getName() == "fread" ||
      F->getName() == "fgets" || F->getName() == "ungetc" ||
      F->getName() == "fputc" ||
      F->getName() == "fputs" || F->getName() == "putc" ||
      F->getName() == "ftell" || F->getName() == "rewind" ||
      F->getName() == "_IO_putc" || F->getName() == "fseek" ||
      F->getName() == "fgetpos" || F->getName() == "fsetpos" ||
      F->getName() == "printf" || F->getName() == "fprintf" ||
      F->getName() == "sprintf" || F->getName() == "vprintf" ||
      F->getName() == "vfprintf" || F->getName() == "vsprintf" ||
      F->getName() == "scanf" || F->getName() == "fscanf" ||
      F->getName() == "sscanf" || F->getName() == "__assert_fail" ||
      F->getName() == "modf")
    return true;

  // These functions do induce points-to edges.
  if (F->getName() == "llvm.memcpy.i32" || F->getName() == "llvm.memcpy.i64" || 
      F->getName() == "llvm.memmove.i32" ||F->getName() == "llvm.memmove.i64" ||
      F->getName() == "memmove") {
    // Note: this is a poor approximation, this says Dest = Src, instead of
    // *Dest = *Src.
    Constraints.push_back(Constraint(Constraint::Copy,
                                     getNode(CS.getArgument(0)),
                                     getNode(CS.getArgument(1)), true));
    return true;
  }

  // Result = Arg0
  if (F->getName() == "realloc" || F->getName() == "strchr" ||
      F->getName() == "strrchr" || F->getName() == "strstr" ||
      F->getName() == "strtok") {
    Constraints.push_back(Constraint(Constraint::Copy,
                                     getNode(CS.getInstruction()),
                                     getNode(CS.getArgument(0)), true));
    return true;
  }

  return false;
}



/// CollectConstraints - This stage scans the program, adding a constraint to
/// the Constraints list for each instruction in the program that induces a
/// constraint, and setting up the initial points-to graph.
///

void Andersens::initglobals(Module &M) {
  // First, the universal set points to itself.
  GraphNodes[UniversalSet].addPointerTo(&GraphNodes[UniversalSet], currentcontext);
  //Constraints.push_back(Constraint(Constraint::Load, &GraphNodes[UniversalSet],
  //                                 &GraphNodes[UniversalSet]));
  Constraints.push_back(Constraint(Constraint::Store, &GraphNodes[UniversalSet],
                                   &GraphNodes[UniversalSet]));

  // Next, the null pointer points to the null object.
  GraphNodes[NullPtr].addPointerTo(&GraphNodes[NullObject], currentcontext);

  // Next, add any constraints on global variables and their initializers.
  for (Module::global_iterator I = M.global_begin(), E = M.global_end();
       I != E; ++I) {
    // Associate the address of the global object as pointing to the memory for
    // the global: &G = <G memory>
    Node *Object = getObject(I);
    Object->setValue(I);
    Object = getNodeValue(*I);	//// CROSS.
    getNodeValue(*I)->addPointerTo(Object, currentcontext);

    if (I->hasInitializer()) {
      AddGlobalInitializerConstraints(Object, I->getInitializer());
    } else {
      // If it doesn't have an initializer (i.e. it's defined in another
      // translation unit), it points to the universal set.
      Constraints.push_back(Constraint(Constraint::Copy, Object,
                                       &GraphNodes[UniversalSet]));
    }
  }
}
int Andersens::processfront(CallSite &cs, CallGraphNode *&p, bool processingspecial) {
  if (p == NULL) return 1;

  CallRecord cr = std::make_pair(cs, p);
  if (processed[cr] || incallchain[p]) {
	//cerr << "this is already processed or cycle.\n";	// currently not iterating over cycles.
	//displaycallchain();
  	return 1;
  }
  processed[cr] = true;
  Function *F = p->getFunction();
  if (!F) {
  	//cerr << "returning from empty fun.\n";
  	return 1;
  }

  currentcontext.callchain.push_back(p);
  currentcontext.cscallchain.push_back(cs);
  //cerr << "moving in call-chain: " << F->getName() << "\n";
  incallchain[p] = true;

  return 0;
}

void Andersens::processback(CallSite &cs, CallGraphNode *p, bool processingspecial) {
  CallRecord cr = std::make_pair(cs, p);
  if (currentcontext.callchain.size() > 0 && incallchain[p]) {
	currentcontext.callchain.pop_back();
	currentcontext.cscallchain.pop_back();
  	incallchain[p] = false;
  }
  processed[cr] = true;
  //cerr << "done this.\n";
}

void Andersens::metavisit(CallSite &cs, CallGraphNode *p) {
    if (p == NULL) return;

    Function *F = p->getFunction();
    if (!F) {
	return;
    }
    if (p != groot) {
        //cerr << "calling addconstforcall.\n";
    	AddConstraintsForCall(cs, F);
        //cerr << "addconstforcall over.\n";
    }
    if (funprocessed[F]) {	// no need to reprocess -- except for arguments/retvals, which is done above.
	return;
    }
    funprocessed[F] = true;	// avoid reprocessing in recursion. Hence this should be set here -- instead of at the end.

    if (!F->isDeclaration()) {
      // Scan the function body, creating a memory object for each heap/stack
      // allocation in the body of the function and a node to represent all
      // pointer values defined by instructions and used as operands.

    bool processingspecial = false;
      //cerr << "calling processfront.\n";
      int frontdideverything = processfront(cs, p, processingspecial);
      if (frontdideverything == 0) {
    	//cerr << "calling visit.\n";
	CallGraphNode *oldcurrentp = currentp;
	currentp = p;
      	visit(F);
      	currentp = oldcurrentp;
    	//cerr << "calling processback.\n";
      	processback(cs, p, processingspecial);
      }
    } else {
      // External functions that return pointers return the universal set.
      //cerr << "ext fun.\n";
      if (isa<PointerType>(F->getFunctionType()->getReturnType()))
        Constraints.push_back(Constraint(Constraint::Copy,
                                         getReturnNode(F),
                                         &GraphNodes[UniversalSet]));

      // Any pointers that are passed into the function have the universal set
      // stored into them.
      for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
           I != E; ++I)
        if (isa<PointerType>(I->getType())) {
          // Pointers passed into external functions could have anything stored
          // through them.
          Constraints.push_back(Constraint(Constraint::Store, getNode(I),
                                           &GraphNodes[UniversalSet]));
          // Memory objects passed into external function calls can have the
          // universal set point to them.
          Constraints.push_back(Constraint(Constraint::Copy,
                                           &GraphNodes[UniversalSet],
                                           getNode(I)));
        }

      // If this is an external varargs function, it can also store pointers
      // into any pointers passed through the varargs section.
      if (F->getFunctionType()->isVarArg())
        Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F),
                                         &GraphNodes[UniversalSet]));
    }
}
void Andersens::AnalyzeCallGraph(BasicCallGraph &CG, Module &M) {
  initglobals(M);
  CallGraphNode *root = CG.getRoot();
  groot = root;
  if (root) {
	metavisit(*new CallSite(), root);
  }
}

void Andersens::visitInstruction(Instruction &I) {
#ifdef NDEBUG
  return;          // This function is just a big assert.
#endif
  if (isa<BinaryOperator>(I))
    return;
  // Most instructions don't have any effect on pointer values.
  switch (I.getOpcode()) {
  case Instruction::Br:
  case Instruction::Switch:
  case Instruction::Unwind:
  case Instruction::Unreachable:
  case Instruction::Free:
  case Instruction::ICmp:
  case Instruction::FCmp:
    return;
  default:
    // Is this something we aren't handling yet?
    cerr << "Unknown instruction: " << I;
    abort();
  }
}

void Andersens::visitAllocationInst(AllocationInst &AI) {
  //cerr << "in alloc.\n";
  getNodeValue(AI)->addPointerTo(getObject(&AI)->setValue(&AI), currentcontext);
}

void Andersens::visitReturnInst(ReturnInst &RI) {
  if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) {
	// return V   -->   <Copy/retval{F}/v>
	Constraints.push_back(Constraint(Constraint::Copy,
                                     getReturnNode(RI.getParent()->getParent()),
                                     getNode(RI.getOperand(0))));
	latestretnode = (void *)getReturnNode(RI.getParent()->getParent());
  } else {
	latestretnode = (void *)NULL;
  }
}

void Andersens::visitLoadInst(LoadInst &LI) {
  //cerr << "in load.\n";
  if (isa<PointerType>(LI.getType()))
    // P1 = load P2  -->  <Load/P1/P2>
    Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI),
                                     getNode(LI.getOperand(0))));
}

void Andersens::visitStoreInst(StoreInst &SI) {
  if (isa<PointerType>(SI.getOperand(0)->getType()))
    // store P1, P2  -->  <Store/P2/P1>
    Constraints.push_back(Constraint(Constraint::Store,
                                     getNode(SI.getOperand(1)),
                                     getNode(SI.getOperand(0))));
}

void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) {
  //cerr << "in gep.\n";
  // P1 = getelementptr P2, ... --> <Copy/P1/P2>
  Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP),
                                   getNode(GEP.getOperand(0))));
}

void Andersens::visitPHINode(PHINode &PN) {
  //cerr << "in phi.\n";
  if (isa<PointerType>(PN.getType())) {
    Node *PNN = getNodeValue(PN);
    for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
      // P1 = phi P2, P3  -->  <Copy/P1/P2>, <Copy/P1/P3>, ...
      Constraints.push_back(Constraint(Constraint::Copy, PNN,
                                       getNode(PN.getIncomingValue(i))));
  }
}

void Andersens::visitCastInst(CastInst &CI) {
  //cerr << "in cast.\n";
  Value *Op = CI.getOperand(0);
  if (isa<PointerType>(CI.getType())) {
    if (isa<PointerType>(Op->getType())) {
      // P1 = cast P2  --> <Copy/P1/P2>
      Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
                                       getNode(CI.getOperand(0))));
    } else {
      // P1 = cast int --> <Copy/P1/Univ>
#if 0
      Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
                                       &GraphNodes[UniversalSet]));
#else
      getNodeValue(CI);
#endif
    }
  } else if (isa<PointerType>(Op->getType())) {
    // int = cast P1 --> <Copy/Univ/P1>
#if 0
    Constraints.push_back(Constraint(Constraint::Copy,
                                     &GraphNodes[UniversalSet],
                                     getNode(CI.getOperand(0))));
#else
    getNode(CI.getOperand(0));
#endif
  }
}

void Andersens::visitSelectInst(SelectInst &SI) {
  //cerr << "in select.\n";
  if (isa<PointerType>(SI.getType())) {
    Node *SIN = getNodeValue(SI);
    // P1 = select C, P2, P3   ---> <Copy/P1/P2>, <Copy/P1/P3>
    Constraints.push_back(Constraint(Constraint::Copy, SIN,
                                     getNode(SI.getOperand(1))));
    Constraints.push_back(Constraint(Constraint::Copy, SIN,
                                     getNode(SI.getOperand(2))));
  }
}

void Andersens::visitVAArg(VAArgInst &I) {
  assert(0 && "vaarg not handled yet!");
}

/// AddConstraintsForCall - Add constraints for a call with actual arguments
/// specified by CS to the function specified by F.  Note that the types of
/// arguments might not match up in the case where this is an indirect call and
/// the function pointer has been casted.  If this is the case, do something
/// reasonable.
void Andersens::AddConstraintsForCall(CallSite CS, Function *F) {
  // If this is a call to an external function, handle it directly to get some
  // taste of context sensitivity.
  //cerr << "calling addconstforextcall.\n";
  if (F && F->isDeclaration() && AddConstraintsForExternalCall(CS, F)) {
    //cerr << "returning from addconstforcall.\n";
    return;
  }
  //cerr << "calling gettype.\n";
  if (isa<PointerType>(CS.getType())) {
    Node *CSN = getNode(CS.getInstruction());
    if (isa<PointerType>(F->getFunctionType()->getReturnType())) {
      Constraints.push_back(Constraint(Constraint::Copy, CSN,
                                       getReturnNode(F), true));
    } else {
      // If the function returns a non-pointer value, handle this just like we
      // treat a nonpointer cast to pointer.
      Constraints.push_back(Constraint(Constraint::Copy, CSN,
                                       &GraphNodes[UniversalSet], true));
    }
  } else {
   if (F && F->getFunctionType() && isa<PointerType>(F->getFunctionType()->getReturnType())) {
    Constraints.push_back(Constraint(Constraint::Copy,
                                     &GraphNodes[UniversalSet],
                                     getReturnNode(F), true));
   }
  }

  Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
  CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end();
  for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI)
    if (isa<PointerType>(AI->getType())) {
      if (isa<PointerType>((*ArgI)->getType())) {
        // Copy the actual argument into the formal argument.
        Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
                                         getNode(*ArgI), true));
      } else {
        Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
                                         &GraphNodes[UniversalSet], true));
      }
    } else if (isa<PointerType>((*ArgI)->getType())) {
      Constraints.push_back(Constraint(Constraint::Copy,
                                       &GraphNodes[UniversalSet],
                                       getNode(*ArgI), true));
    }

  // Copy all pointers passed through the varargs section to the varargs node.
  if (F->getFunctionType()->isVarArg())
    for (; ArgI != ArgE; ++ArgI)
      if (isa<PointerType>((*ArgI)->getType()))
        Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F),
                                         getNode(*ArgI), true));
  // If more arguments are passed in than we track, just drop them on the floor.
  //cerr << "addconstforcall exit.\n";
}

void Andersens::visitCallSite(CallSite CS) {
  //cerr << "invisitcallsite.\n";
  if (isa<PointerType>(CS.getType()))
    getNodeValue(*CS.getInstruction());

  if (Function *F = CS.getCalledFunction()) {
    if (currentp) {
	    CallGraphNode *p = NULL;
	    for (unsigned ii = 0; ii < currentp->CalledFunctions.size(); ++ii) {
		if (currentp->CalledFunctions[ii].second && currentp->CalledFunctions[ii].second->getFunction() == F && currentp->CalledFunctions[ii].first.getInstruction() == CS.getInstruction()) {	//// also check for CS == currentp->CalledFunctions[ii].first. we may need to do getInstruction() on both sides of ==.
			p = currentp->CalledFunctions[ii].second;
			break;
		}
	    }
	    if (p) {
	    	    //cerr << "calling metavisit from visitcallsite.\n";
	    	    metavisit(CS, p);
		    //cerr << "no of operands of callinst = " << CS.getInstruction()->getNumOperands() << ".\n";
      		    if (F->getFunctionType() && isa<PointerType>(F->getFunctionType()->getReturnType()) && CS.getInstruction()->getNumOperands() && latestretnode) {
			Constraints.push_back(Constraint(Constraint::Copy,
                                     //getReturnNode(CS.getParent()->getParent()),
				     getNode(CS.getInstruction()),
                                     (Node *)latestretnode));
		    }
		    latestretnode = (void *)NULL;
	    } else {
		//cerr << "\tnot calling metavisit. no such callsite1 or in cycle hierarchy.\n";
	    }
    }
  } else {
    // We don't handle indirect call sites yet.  Keep track of them for when we
    // discover the call graph incrementally.
    if (currentp) {
	    CallGraphNode *p = NULL;
	    for (unsigned ii = 0; ii < currentp->CalledFunctions.size(); ++ii) {
		if (currentp->CalledFunctions[ii].first.getInstruction() == CS.getInstruction()) {
			p = currentp->CalledFunctions[ii].second;
			break;
		}
	    }
	    if (p) {
	    	    //cerr << "calling metavisit from visitcallsite.\n";
	    	    metavisit(CS, p);
		    //cerr << "no of operands of callinst2 = " << CS.getInstruction()->getNumOperands() << ".\n";
      		    if (CS.getInstruction()->getNumOperands() && latestretnode) {
			Constraints.push_back(Constraint(Constraint::Copy,
                                     //getReturnNode(CS.getParent()->getParent()),
				     getNode(CS.getInstruction()),
                                     (Node *)latestretnode));
		    }
		    latestretnode = (void *)NULL;
	    } else {
		//cerr << "\tnot calling metavisit. no such callsite2.\n";
	    }
    }
    IndirectCalls.push_back(CS);
  }
}

//===----------------------------------------------------------------------===//
//                         Constraint Solving Phase
//===----------------------------------------------------------------------===//

/// intersects - Return true if the points-to set of this node intersects
/// with the points-to set of the specified node.
bool Andersens::Node::intersects(Node *N) const {
  iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end();
  while (I1 != E1 && I2 != E2) {
    if (*I1 == *I2) return true;
    if (*I1 < *I2)
      ++I1;
    else
      ++I2;
  }
  return false;
}

bool Andersens::Node::issubset(const std::vector<CallSite> &s1, const std::vector<CallSite> &s2) const {
	for (unsigned ii = 0, jj = 0; ii < s1.size() && jj < s2.size(); ++ii, ++jj) {
		if (s1[ii].getInstruction() != s2[jj].getInstruction()) {
			return false;
		}
	}
	return true;
}
bool Andersens::Node::issubset(const One &s1, const One &s2) const {
	for (unsigned ii = 0, jj = 0; ii < s1.size() && jj < s2.size(); ++ii, ++jj) {
		if (s1[ii] < s2[jj] || s1[ii] > s2[jj]) {
			return false;
		}
	}
	return true;
}
/// intersectsIgnoring - Return true if the points-to set of this node
/// intersects with the points-to set of the specified node on any nodes
/// except for the specified node to ignore.
bool Andersens::Node::intersectsIgnoring(Node *N, Node *Ignoring) const {
  std::map<One, Two *>::const_iterator it1 = this->contexts.begin();
  std::map<One, Two *>::const_iterator it2 = N->contexts.begin();
  std::map<One, Two *>::const_iterator it1end = this->contexts.end();
  std::map<One, Two *>::const_iterator it2end = N->contexts.end();
  for (; it1 != it1end; ++it1) {
	for (it2=N->contexts.begin(), it2end=N->contexts.end(); it2 != it2end; ++it2) {
		if (issubset(it1->first, it2->first)) {
		//if (issubset(it1->first, it2->first) && issubset(it1->second->cscallchain, it2->second->cscallchain)) {
			  iterator I1=currentcontext.Pointees.end(), I2=currentcontext.Pointees.end(), E1=currentcontext.Pointees.end(), E2=currentcontext.Pointees.end();
			  if (it1->second && it2->second) {
			  	I1 = it1->second->Pointees.begin(), I2 = it2->second->Pointees.begin(), E1 = it1->second->Pointees.end(), E2 = it2->second->Pointees.end();
			  }
			  while (I1 != E1 && I2 != E2) {
			    //cerr << "\t\t\t comparing " << (*I1 && (*I1)->getValue() ? (*I1)->getValue()->getName() : "NULL") << " vs " << (*I2 && (*I2)->getValue() ? (*I2)->getValue()->getName() : "NULL") << "\n";
			    if (*I1 == *I2) {
			      if (*I1 != Ignoring) return true;
			      ++I1; ++I2;
			    } else if (*I1 < *I2)
			      ++I1;
			    else
			      ++I2;
			  }
		}
	}
  }
  return false;
}

// Copy constraint: all edges out of the source node get copied to the
// destination node.  This returns true if a change is made.
bool Andersens::Node::copyFrom(Node *N, const Andersens::CrossContext &dstcontext, const Andersens::CrossContext &srccontext) {

  return cross_copyfrom(this, N, const_cast<Andersens::CrossContext &>(dstcontext));

  // Use a mostly linear-time merge since both of the lists are sorted.
	Andersens::CrossContext *ccdst = this->contexts[dstcontext.callchain];
	if (!ccdst) {
		ccdst = this->contexts[dstcontext.callchain] = new Andersens::CrossContext();
		ccdst->callchain = dstcontext.callchain;
		ccdst->cscallchain = dstcontext.cscallchain;
	}
	Andersens::CrossContext *ccsrc = N->contexts[srccontext.callchain];
	if (!ccsrc) {
		ccsrc = N->contexts[srccontext.callchain] = new Andersens::CrossContext();
		ccsrc->callchain = srccontext.callchain;
		ccsrc->cscallchain = srccontext.cscallchain;
	}

  bool Changed = false;
  iterator I = ccsrc->Pointees.begin(), E = ccsrc->Pointees.end();
  unsigned i = 0;
  while (I != E && i != ccdst->Pointees.size()) {
    if (ccdst->Pointees[i] < *I) {
      ++i;
    } else if (ccdst->Pointees[i] == *I) {
      ++i; ++I;
    } else {
      // We found a new element to copy over.
      Changed = true;
      ccdst->Pointees.insert(ccdst->Pointees.begin()+i, *I);
       ++i; ++I;
    }
  }

  if (I != E) {
    ccdst->Pointees.insert(ccdst->Pointees.end(), I, E);
    Changed = true;
  }

  return Changed;
}

bool Andersens::Node::loadFrom(Node *N, Andersens::CrossContext &dstcontext, Andersens::CrossContext &srccontext) {
  bool Changed = false;
  /*iterator I = currentcontext.Pointees.end(), E = currentcontext.Pointees.end();
  if (N->contexts[dstcontext.callchain]) {
      I = N->contexts[dstcontext.callchain]->Pointees.begin();
      E = N->contexts[dstcontext.callchain]->Pointees.end();
  }
  for (; I != E; ++I)
    Changed |= copyFrom(*I, emptycontext, srccontext);*/
  	Changed |= copyFrom(N, emptycontext, srccontext);	// this is for p = tmp;
  return Changed;
}

bool Andersens::Node::storeThrough(Node *N, Andersens::CrossContext &dstcontext, Andersens::CrossContext &srccontext) {
  bool Changed = false;
  /*iterator I = currentcontext.Pointees.end(), E = currentcontext.Pointees.end();
  if (this->contexts[dstcontext.callchain]) {
      I = this->contexts[dstcontext.callchain]->Pointees.begin();
      E = this->contexts[dstcontext.callchain]->Pointees.end();
  }
  for (; I != E; ++I)
    Changed |= (*I)->copyFrom(N, emptycontext, srccontext);*/
  	addPointerTo(N, const_cast<Andersens::CrossContext &>(emptycontext));		// this is for p = &x.
  	Changed |= copyFrom(N, emptycontext, srccontext);	// this is for p = tmp;
  return Changed;
}


/// SolveConstraints - This stage iteratively processes the constraints list
/// propagating constraints (adding edges to the Nodes in the points-to graph)
/// until a fixed point is reached.
///
#define CONTEXT_CONFLICT	1
#define CONTEXT_EQUAL		2
#define CONTEXT_SUBSET		3
#define CONTEXT_SUPERSET	4
#define CONTEXT_UNRELATED	5

std::map<Andersens::One, bool> pc;
std::map<std::vector<CallSite>, bool> pcs;

int getrelationship(const Andersens::One &ccone, const Andersens::One &cctwo, const std::vector<CallSite> &csone, const std::vector<CallSite> &cstwo) {
	unsigned ii;
	for (ii = 0; ii < ccone.size() && ii < cctwo.size() && ii < csone.size() && ii < cstwo.size(); ++ii) {
		if (ccone[ii] == cctwo[ii] && csone[ii].getInstruction() == cstwo[ii].getInstruction()) continue;
		else if (ccone[ii] == cctwo[ii] && csone[ii].getInstruction() != cstwo[ii].getInstruction()) return CONTEXT_CONFLICT;
		else if (ccone[ii] != cctwo[ii]) return CONTEXT_UNRELATED;
	}
	if (ii == ccone.size() && ii == cctwo.size()) return CONTEXT_EQUAL;
	else if (ii == ccone.size()) return CONTEXT_SUBSET;
	else return CONTEXT_SUPERSET;
}
int getrelationship(Andersens::CrossContext &one, Andersens::CrossContext &two) {
	return getrelationship(one.callchain, two.callchain, one.cscallchain, two.cscallchain);
}
bool processedcontext(Andersens::CrossContext &context) {
	if (pc[context.callchain] && pcs[context.cscallchain]) return true;
	// check whether a superset of the context is processed.
	std::map<Andersens::One, bool>::iterator itcc = pc.begin();
	std::map<std::vector<CallSite>, bool>::iterator itcs = pcs.begin();
	for (; itcc != pc.end() && itcs != pcs.end(); ++itcc, ++itcs) {
		if (getrelationship(context.callchain, itcc->first, context.cscallchain, itcs->first) == CONTEXT_SUBSET) return true;
	}
	return false;
}
bool islocal(Andersens::Node *nn) {
	if (nn) {
		Value *vv = nn->getValue();
		if (vv && vv->getName().find("tmp") == 0) {
			return true;
		}
	}
	return false;
}
void Andersens::SolveConstraints() {
  unsigned Iteration = 0;
  //clock_t cross_starttime, cross_endtime;

 for (unsigned outeri = 0, outere = Constraints.size(); outeri != outere; ++outeri) {
  CrossContext contextbeingprocessed = Constraints[outeri].context;
  if (processedcontext(contextbeingprocessed)) {
	continue;
  }
  bool Changed = true;
  while (Changed) {
    Changed = false;
    ++NumIters;
    DOUT << "Starting iteration #" << Iteration++ << "!\n";

    // Loop over all of the constraints, applying them in turn.
    for (unsigned i = outeri, e = Constraints.size(); i != e; ++i) {
      Constraint &C = Constraints[i];
      int contextrelationship = getrelationship(C.context, contextbeingprocessed);	// take care of empty context.
      if (contextrelationship == CONTEXT_CONFLICT) {
	continue;
      } else if (contextrelationship == CONTEXT_SUPERSET) {
	contextbeingprocessed = C.context;
      } else {	// CONTEXT_EQUAL || CONTEXT_SUBSET || CONTEXT_UNRELATED.

      }
	//cross_starttime = clock();
      switch (C.Type) {
      case Constraint::Copy:
        Changed |= C.Dest->copyFrom(C.Src, contextbeingprocessed, C.context);
        break;
      case Constraint::Load:
        Changed |= C.Dest->loadFrom(C.Src, contextbeingprocessed, C.context);
        break;
      case Constraint::Store:
        Changed |= C.Dest->storeThrough(C.Src, contextbeingprocessed, C.context);
        break;
      default:
        assert(0 && "Unknown constraint!");
      }
	/*cross_endtime = clock();
	cross_bloomtime += cross_endtime - cross_starttime;*/
    }

    if (Changed) {
      // Check to see if any internal function's addresses have been passed to
      // external functions.  If so, we have to assume that their incoming
      // arguments could be anything.  If there are any internal functions in
      // the universal node that we don't know about, we must iterate.
      //for (Node::iterator I = GraphNodes[UniversalSet].begin(),
        //     E = GraphNodes[UniversalSet].end(); I != E; ++I)
      Node::iterator I, E;
      for (std::map<One, Two*>::const_iterator it = GraphNodes[UniversalSet].contexts.begin(); it != GraphNodes[UniversalSet].contexts.end(); ++it) {
       if (it->second) {
	  I = it->second->Pointees.begin();
	  E = it->second->Pointees.end();
       } else {
	  continue;
       }
       for (; I != E; ++I)
        if (Function *F = dyn_cast_or_null<Function>((*I)->getValue()))
          if (F->hasInternalLinkage() &&
              EscapingInternalFunctions.insert(F).second) {
            // We found a function that is just now escaping.  Mark it as if it
            // didn't have internal linkage.
            AddConstraintsForNonInternalLinkage(F);
            DOUT << "Found escaping internal function: " << F->getName() <<"\n";
            ++NumEscapingFunctions;
          }
      }

      // Check to see if we have discovered any new callees of the indirect call
      // sites.  If so, add constraints to the analysis.
      for (unsigned i = 0, e = IndirectCalls.size(); i != e; ++i) {
        CallSite CS = IndirectCalls[i];
        std::vector<Function*> &KnownCallees = IndirectCallees[CS];
        Node *CN = getNode(CS.getCalledValue());

      Node::iterator NI, E;
      for (std::map<One, Two*>::const_iterator it = CN->contexts.begin(); it != CN->contexts.end(); ++it) {
       if (it->second) {
	  NI = it->second->Pointees.begin();
	  E = it->second->Pointees.end();
       } else {
	  continue;
       }
	for (; NI != E; ++NI) 
          if (Function *F = dyn_cast_or_null<Function>((*NI)->getValue())) {
            std::vector<Function*>::iterator IP =
              std::lower_bound(KnownCallees.begin(), KnownCallees.end(), F);
            if (IP == KnownCallees.end() || *IP != F) {
              // Add the constraints for the call now.
              AddConstraintsForCall(CS, F);
              DOUT << "Found actual callee '"
                   << F->getName() << "' for call: "
                   << *CS.getInstruction() << "\n";
              ++NumIndirectCallees;
              KnownCallees.insert(IP, F);
            }
          }
	}
      }
    }
  }
  pc[contextbeingprocessed.callchain] = true;
  pcs[contextbeingprocessed.cscallchain] = true;
 }
 //cout << "nconstraints = " << Constraints.size() << "\n";
}



//===----------------------------------------------------------------------===//
//                               Debugging Output
//===----------------------------------------------------------------------===//

void Andersens::PrintNode(Node *N) {
  if (N == &GraphNodes[UniversalSet]) {
    cerr << "<universal>";
    return;
  } else if (N == &GraphNodes[NullPtr]) {
    cerr << "<nullptr>";
    return;
  } else if (N == &GraphNodes[NullObject]) {
    cerr << "<null>";
    return;
  }

  if (N->getValue() == 0) {
	cerr << "NULL ";
	return;
  }
  //assert(N->getValue() != 0 && "Never set node label!");
  Value *V = N->getValue();
  if (Function *F = dyn_cast<Function>(V)) {
    if (isa<PointerType>(F->getFunctionType()->getReturnType()) &&
        N == getReturnNode(F)) {
      cerr << F->getName() << ":retval";
      return;
    } else if (F->getFunctionType()->isVarArg() && N == getVarargNode(F)) {
      cerr << F->getName() << ":vararg";
      return;
    }
  }

  if (Instruction *I = dyn_cast<Instruction>(V))
    cerr << I->getParent()->getParent()->getName() << ":";
  else if (Argument *Arg = dyn_cast<Argument>(V))
    cerr << Arg->getParent()->getName() << ":";

  if (V->hasName())
    cerr << V->getName();
  else
    cerr << "(unnamed)";

  if (isa<GlobalValue>(V) || isa<AllocationInst>(V))
    if (N == getObject(V))
      cerr << "<mem>";
}

void Andersens::PrintConstraints() {
  cerr << "Constraints:\n";
  for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
    cerr << "  #" << i << ":  ";
    Constraint &C = Constraints[i];
    if (C.Type == Constraint::Store)
      cerr << "*";
    PrintNode(C.Dest);
    cerr << " = ";
    if (C.Type == Constraint::Load)
      cerr << "*";
    PrintNode(C.Src);
    cerr << "\n";
  }
}

void Andersens::printcontext(const One &context) {
	cerr << "\t ";
	for (One::const_iterator it = context.begin(); it != context.end(); ++it) {
		cerr << (*it)->getFunction()->getName() << "-";
	}
}
void Andersens::printpointees(Two *context) {
	cerr << ": ";
	for (std::vector<Node *>::iterator it = context->Pointees.begin(); it != context->Pointees.end(); ++it) {
		//cerr << (*it)->getValue()->getName() << ", ";
		PrintNode(*it);
		cerr << ", ";
	}
        cerr << "\n";
}
void Andersens::PrintPointsToGraph() {
  cerr << "Points-to graph:\n";
  for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) {
    Node *N = &GraphNodes[i];
    //cerr << "[" << (N->end() - N->begin()) << "] ";
    cerr << "[" << N->contexts.size() << "] ";
    PrintNode(N);
    cerr << "\t-->\n";
    std::map<One, Two *>::const_iterator it = N->contexts.begin();
    for (; it != N->contexts.end(); ++it) {
	printcontext(it->first);
	printpointees(it->second);
    }
    /*for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
      if (I != N->begin()) cerr << ", ";
      PrintNode(*I);
    }*/
    //cerr << "\n";
  }
}
void Andersens::findderefsize() {
	unsigned nderef = 0;
	for (unsigned ii = 0; ii < GraphNodes.size(); ++ii) {
		nderef += GraphNodes[ii].getsize();
	}
	//cerr << "deref size = " << nderef << "/" << GraphNodes.size() << " = " << (float)nderef/GraphNodes.size() << ".\n";
}
